{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Most Beautiful Item for Each Query"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumBeauty"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #每一个查询的最大美丽值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二维整数数组&nbsp;<code>items</code>&nbsp;，其中&nbsp;<code>items[i] = [price<sub>i</sub>, beauty<sub>i</sub>]</code>&nbsp;分别表示每一个物品的 <strong>价格</strong>&nbsp;和 <strong>美丽值</strong>&nbsp;。</p>\n",
    "\n",
    "<p>同时给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>queries</code>&nbsp;。对于每个查询&nbsp;<code>queries[j]</code>&nbsp;，你想求出价格小于等于&nbsp;<code>queries[j]</code>&nbsp;的物品中，<strong>最大的美丽值</strong>&nbsp;是多少。如果不存在符合条件的物品，那么查询的结果为&nbsp;<code>0</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回一个长度与 <code>queries</code>&nbsp;相同的数组<em>&nbsp;</em><code>answer</code>，其中<em>&nbsp;</em><code>answer[j]</code>是第&nbsp;<code>j</code>&nbsp;个查询的答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>items = [[1,2],[3,2],[2,4],[5,6],[3,5]], queries = [1,2,3,4,5,6]\n",
    "<b>输出：</b>[2,4,5,5,6,6]\n",
    "<strong>解释：</strong>\n",
    "- queries[0]=1 ，[1,2] 是唯一价格 &lt;= 1 的物品。所以这个查询的答案为 2 。\n",
    "- queries[1]=2 ，符合条件的物品有 [1,2] 和 [2,4] 。\n",
    "  它们中的最大美丽值为 4 。\n",
    "- queries[2]=3 和 queries[3]=4 ，符合条件的物品都为 [1,2] ，[3,2] ，[2,4] 和 [3,5] 。\n",
    "  它们中的最大美丽值为 5 。\n",
    "- queries[4]=5 和 queries[5]=6 ，所有物品都符合条件。\n",
    "  所以，答案为所有物品中的最大美丽值，为 6 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>items = [[1,2],[1,2],[1,3],[1,4]], queries = [1]\n",
    "<b>输出：</b>[4]\n",
    "<b>解释：</b>\n",
    "每个物品的价格均为 1 ，所以我们选择最大美丽值 4 。\n",
    "注意，多个物品可能有相同的价格和美丽值。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>items = [[10,1000]], queries = [5]\n",
    "<b>输出：</b>[0]\n",
    "<strong>解释：</strong>\n",
    "没有物品的价格小于等于 5 ，所以没有物品可以选择。\n",
    "因此，查询的结果为 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= items.length, queries.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>items[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= price<sub>i</sub>, beauty<sub>i</sub>, queries[j] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [most-beautiful-item-for-each-query](https://leetcode.cn/problems/most-beautiful-item-for-each-query/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [most-beautiful-item-for-each-query](https://leetcode.cn/problems/most-beautiful-item-for-each-query/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2],[3,2],[2,4],[5,6],[3,5]]\\n[1,2,3,4,5,6]', '[[1,2],[1,2],[1,3],[1,4]]\\n[1]', '[[10,1000]]\\n[5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        items.sort(reverse=True)\n",
    "        queries = sorted([(q, i) for i, q in enumerate(queries)])\n",
    "        \n",
    "        maxval = 0\n",
    "        ans = [0] * len(queries)\n",
    "        for q, i in queries:\n",
    "            while items and items[-1][0] <= q:\n",
    "                _, v = items.pop()\n",
    "                maxval = max(maxval, v)\n",
    "            ans[i] = maxval\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        items.sort(key=lambda x:(-x[0],x[1]))\n",
    "        n=len(queries)\n",
    "        ans=[0]*n\n",
    "        temp=list(range(n))\n",
    "        temp.sort(key=lambda x:queries[x])\n",
    "        s=SortedList()\n",
    "        for i in range(n):\n",
    "            while items and items[-1][0]<=queries[temp[i]]:\n",
    "                x,y=items.pop()\n",
    "                s.add(y)\n",
    "            if len(s)>0:\n",
    "                ans[temp[i]]=s[-1]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "      subjectDict = collections.defaultdict(int)\n",
    "      for price, value in items:\n",
    "        subjectDict[price] = max(subjectDict[price], value)\n",
    "      \n",
    "      items = [[0, 0]] + sorted([k, v] for k, v in subjectDict.items())\n",
    "      n = len(items)\n",
    "      for i in range(1, n):\n",
    "        items[i][1] = max(items[i][1], items[i-1][1])\n",
    "      \n",
    "      for i in range(len(queries)):\n",
    "        L, R = 0, n-1\n",
    "        while L <= R:\n",
    "          mid = (L + R) // 2\n",
    "          if items[mid][0] <= queries[i]:\n",
    "            L = mid + 1\n",
    "          else:\n",
    "            R = mid - 1\n",
    "        queries[i] = items[L-1][1]\n",
    "      return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "      subjectDict = collections.defaultdict(int)\n",
    "      for price, value in items:\n",
    "        subjectDict[price] = max(subjectDict[price], value)\n",
    "      \n",
    "      items = [[0, 0]] + sorted([k, v] for k, v in subjectDict.items())\n",
    "      n = len(items)\n",
    "      for i in range(1, n):\n",
    "        items[i][1] = max(items[i][1], items[i-1][1])\n",
    "      \n",
    "      for i in range(len(queries)):\n",
    "        L, R = 0, n-1\n",
    "        while L <= R:\n",
    "          mid = (L + R) // 2\n",
    "          if items[mid][0] <= queries[i]:\n",
    "            L = mid + 1\n",
    "          else:\n",
    "            R = mid - 1\n",
    "        queries[i] = items[L-1][1]\n",
    "      return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        # 将物品按价格升序排序\n",
    "        items.sort(key=lambda x: x[0])\n",
    "        n = len(items)\n",
    "        # 按定义修改美丽值\n",
    "        for i in range(1, n):\n",
    "            items[i][1] = max(items[i][1], items[i-1][1])\n",
    "        # 二分查找处理查询\n",
    "        def query(q: int) -> int:\n",
    "            l, r = 0, n\n",
    "            while l < r:\n",
    "                mid = l + (r - l) // 2\n",
    "                if items[mid][0] > q:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            if l == 0:\n",
    "                # 此时所有物品价格均大于查询价格\n",
    "                return 0\n",
    "            else:\n",
    "                # 返回小于等于查询价格的物品的最大美丽值\n",
    "                return items[l-1][1]\n",
    "        \n",
    "        res = [query(q) for q in queries]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        # 将物品按价格升序排序\n",
    "        items.sort(key=lambda x: x[0])\n",
    "        n = len(items)\n",
    "        # 按定义修改美丽值\n",
    "        for i in range(1, n):\n",
    "            items[i][1] = max(items[i][1], items[i-1][1])\n",
    "        # 二分查找处理查询\n",
    "        def query(q: int) -> int:\n",
    "            l, r = 0, n\n",
    "            while l < r:\n",
    "                mid = l + (r - l) // 2\n",
    "                if items[mid][0] > q:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            if l == 0:\n",
    "                # 此时所有物品价格均大于查询价格\n",
    "                return 0\n",
    "            else:\n",
    "                # 返回小于等于查询价格的物品的最大美丽值\n",
    "                return items[l-1][1]\n",
    "        \n",
    "        res = [query(q) for q in queries]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        ans = list()\n",
    "        items.sort(key = lambda z: z[0])\n",
    "        n = len(items)\n",
    "        for i in range(1, n):\n",
    "            items[i][1] = max(items[i][1], items[i-1][1])\n",
    "\n",
    "        def tbinary(q: int) -> int:\n",
    "            left, right = 0, n\n",
    "            while left < right:\n",
    "                mid = (left + right) //2\n",
    "                if items[mid][0] > q:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "\n",
    "            if right == 0:\n",
    "                return 0\n",
    "            else:\n",
    "                return items[left - 1][1]\n",
    "\n",
    "        ans = [tbinary(q) for q in queries]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        items.sort(key = lambda x: x[0])\n",
    "        for i in range(1, len(items)):\n",
    "            items[i][1] = max(items[i][1], items[i-1][1])\n",
    "        result = [self.query(items, i) for i in queries]\n",
    "        return result\n",
    "\n",
    "    # 二分法找i对应的price\n",
    "    def query(self, items, i):\n",
    "        l, r= 0, len(items)\n",
    "        while l<r:\n",
    "            mid = l + (r-l) //2\n",
    "            if items[mid][0] > i:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        if l == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            return items[l-1][1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        def query(target):\n",
    "            l,r = 0,len(items)\n",
    "            while l < r:\n",
    "                mid = (l+r)//2\n",
    "                if items[mid][0] > target:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            if l == 0:\n",
    "                return 0\n",
    "            else:\n",
    "                return items[l-1][1]\n",
    "        items.sort()\n",
    "        n = len(items)\n",
    "        for i in range(1, n):\n",
    "            items[i][1] = max(items[i][1], items[i-1][1])\n",
    "        return [query(q) for q in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        items.sort(key=lambda x: x[0])\n",
    "        n = len(items)\n",
    "        for i in range(1, n):\n",
    "            items[i][1] = max(items[i][1], items[i - 1][1])\n",
    "        def query(q: int) -> int:\n",
    "            l, r = 0, n\n",
    "            while l < r:\n",
    "                mid = l + (r - l) // 2\n",
    "                if items[mid][0] > q:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            if l == 0:\n",
    "                # 此时所有物品价格均大于查询价格\n",
    "                return 0\n",
    "            else:\n",
    "                # 返回小于等于查询价格的物品的最大美丽值\n",
    "                return items[l-1][1]\n",
    "        \n",
    "        res = [query(q) for q in queries]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        # 题意\n",
    "        # 每一次查询找到价格小于等于q的最大美丽值\n",
    "        # 如果不存在价格小于等于q的话那么返回0\n",
    "        # 想法二分\n",
    "        # 首先把每个价格的最大美丽值存储起来，然后查询在这个数据结构中它的下标\n",
    "        # g = defaultdict(int)\n",
    "        # for price, beauty in items:\n",
    "        #     g[price] = max(g[price],beauty)\n",
    "        # g.sort()\n",
    "        # ans = [0]*len(queries)\n",
    "        # for i,q in enumerate(queries):\n",
    "        #     index = bisect_right(g,q)\n",
    "        #         if index != 0:\n",
    "        #             ans[i] = g[index]\n",
    "        # return ans\n",
    "        n = len(items)\n",
    "        items.sort(key = lambda x:x[0])\n",
    "        # 将美丽值修改为小于等于价格的最大值\n",
    "        for i in range(1,n):\n",
    "            items[i][1] = max(items[i][1],items[i-1][1])\n",
    "        # 查询\n",
    "        def query(q):\n",
    "            l,r = 0,n\n",
    "            while l < r:\n",
    "                mid = (l+r)//2\n",
    "                if items[mid][0] > q:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid+1\n",
    "            if l == 0:\n",
    "                return 0\n",
    "            else:\n",
    "                return items[l-1][1]\n",
    "        ans = [query(q) for q in queries]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        # 排序\n",
    "        # 更新美丽值\n",
    "        n = len(items)\n",
    "        items.sort(key = lambda x:x[0])\n",
    "        for i in range(1,n):\n",
    "            items[i][1] = max(items[i][1],items[i-1][1])\n",
    "        # 二分\n",
    "        def query(q):\n",
    "            left = 0\n",
    "            right = n-1\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                if items[mid][0] <= q:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            if left == 0:\n",
    "                return 0\n",
    "            return items[left-1][1]\n",
    "        # 统计结果\n",
    "        ans = [query(q) for q in queries]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        m = len(queries)\n",
    "        ans = [0]*m\n",
    "        ind = list(range(m))\n",
    "        ind.sort(key=lambda it: queries[it])\n",
    "        items.sort()\n",
    "        n = len(items)\n",
    "        j = 0\n",
    "        pre= 0\n",
    "        for i in ind:\n",
    "            q = queries[i]\n",
    "            while j<n and items[j][0] <= q:\n",
    "                x = items[j][1]\n",
    "                if x > pre:\n",
    "                    pre = x\n",
    "                j += 1\n",
    "            ans[i] = pre\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        n = len(items)\n",
    "        ans = [0] * len(queries)\n",
    "        items.sort(key=lambda x: x[0])\n",
    "        maxItems = [0] * (n + 1)\n",
    "        for i, item in enumerate(items):\n",
    "            maxItems[i+1] = max(maxItems[i], item[1])\n",
    "        def search(q: int) -> int:\n",
    "            l, r = 0, n\n",
    "            while l < r:\n",
    "                mid = (l + r) // 2\n",
    "                if items[mid][0] < q:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid\n",
    "            return l\n",
    "        for i, q in enumerate(queries):\n",
    "            ans[i] = maxItems[search(q + 1)]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        d = {}\n",
    "        pr = set()\n",
    "        for p, b in items:\n",
    "            d[p] = max(b, d.get(p, 0))\n",
    "            pr.add(p)\n",
    "        pr = [[0, 0]] + [[x, d[x]] for x in sorted(list(set(pr)))]\n",
    "        for i in range(1, len(pr)):\n",
    "            pr[i][1] = max(pr[i][1], pr[i - 1][1])\n",
    "        n = len(queries)\n",
    "        ans = [0] * n \n",
    "        for i, x in enumerate(queries):\n",
    "            ans[i] = pr[bisect_right(pr, [x, inf]) - 1][1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        items.sort()\n",
    "        lst1, lst2 = zip(*items)\n",
    "        lst2 = list(accumulate(lst2, func = max, initial = 0))\n",
    "        return [lst2[bisect.bisect_right(lst1, q)] for q in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        items.sort()\n",
    "        lst1, lst2 = zip(*items)\n",
    "        lst2 = list(accumulate(lst2, func = max, initial = 0))\n",
    "        return [lst2[bisect.bisect_right(lst1, q)] for q in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 二分找右边界\n",
    "def rightBound(a: List[int], t: int) -> int:\n",
    "    l, r = 0, len(a) - 1\n",
    "    while l < r:\n",
    "        mid = (l + r + 1) >> 1\n",
    "        if a[mid] > t:\n",
    "            r = mid - 1\n",
    "        else:\n",
    "            l = mid\n",
    "    return -1 if a[l] > t else l\n",
    "    \n",
    "class Solution:\n",
    "    '''\n",
    "        排序 + 二分\n",
    "    '''\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        n = len(items)\n",
    "        idx = [0] * n\n",
    "        price = [0] * n\n",
    "        for i in range(n):\n",
    "            idx[i] = i\n",
    "            price[i] = items[i][0]\n",
    "        price.sort()\n",
    "        idx.sort(key=lambda x: items[x][0])\n",
    "        max_b = [0] * n                 # 预处理max_beauty 为一段区间的最大的美丽值\n",
    "        max_b[0] = items[idx[0]][1]\n",
    "        for i in range(1, n):\n",
    "            max_b[i] = max(max_b[i - 1], items[idx[i]][1])\n",
    "        print(max_b)\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            index = rightBound(price, q)\n",
    "            if index == -1:\n",
    "                ans.append(0)\n",
    "            else:\n",
    "                ans.append(max_b[index])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        items.sort()\n",
    "        dp = [0]*len(items)\n",
    "        dp[0] = items[0][1]\n",
    "        for i in range(1,len(dp)):\n",
    "            if items[i][1] > dp[i-1]:\n",
    "                dp[i] = items[i][1]\n",
    "            else:\n",
    "                dp[i] = dp[i-1]\n",
    "        # 小于等于返回True \n",
    "        def check(x,i):\n",
    "            if items[x][0] <= i:\n",
    "                return True \n",
    "            else:\n",
    "                return False \n",
    "        \n",
    "        res = []\n",
    "        for i in queries:\n",
    "            # 二分\n",
    "            left = 0\n",
    "            right = len(items) - 1\n",
    "            while left <= right:\n",
    "                mid = (left+right) >> 1\n",
    "                if check(mid,i):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            if right >= 0:\n",
    "                res.append(dp[right])\n",
    "            else:\n",
    "                res.append(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        items.sort()\n",
    "        n = len(items)\n",
    "        lp = [0] * n\n",
    "        lb = [0] * n\n",
    "        maxb = 0\n",
    "        for i in range(n):\n",
    "            maxb = max(maxb, items[i][1])\n",
    "            lp[i] = items[i][0]\n",
    "            lb[i] = maxb\n",
    "\n",
    "        n = len(queries)\n",
    "        ret = []\n",
    "        for i in range(n):\n",
    "            idx = bisect.bisect_right(lp, queries[i]) - 1\n",
    "            if idx == -1:\n",
    "                ret.append(0)\n",
    "            else:\n",
    "                ret.append(lb[idx])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * (n + 1)\n",
    "    \n",
    "    def update(self, i, mx):\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] = max(self.tree[i], mx)\n",
    "            i += i & -i\n",
    "    \n",
    "    def query(self, i):\n",
    "        mx = -inf\n",
    "        while i:\n",
    "            mx = max(mx, self.tree[i])\n",
    "            i -= i & -i\n",
    "        return mx\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        items.sort()\n",
    "        qs = sorted((q, i) for i, q in enumerate(queries))\n",
    "        i, n = 0, len(items)\n",
    "        mx = 0\n",
    "        res = [0] * len(queries)\n",
    "        for q, qi in qs:\n",
    "            while i < n and items[i][0] <= q:\n",
    "                mx = max(mx, items[i][1])\n",
    "                i += 1\n",
    "            res[qi] = mx\n",
    "        return res\n",
    "\n",
    "        # items.sort()\n",
    "        # qs = sorted((q, i) for i, q in enumerate(queries))\n",
    "        # i, n = 0, len(items)\n",
    "        # s = set(p for p, _ in items) | set(queries)\n",
    "        # mp = {x: i + 1 for i, x in enumerate(sorted(s))}\n",
    "        # bit = BIT(len(mp))\n",
    "        # res = [0] * len(queries)\n",
    "        # for q, qi in qs:\n",
    "        #     while i < n and items[i][0] <= q:\n",
    "        #         bit.update(mp[items[i][0]], items[i][1])\n",
    "        #         i += 1\n",
    "        #     res[qi] = bit.query(mp[q])\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        items.sort(key = lambda x: (x[0], -x[1]))\n",
    "        import bisect \n",
    "        beauties = []\n",
    "        prices = []\n",
    "        maxValue = 0\n",
    "        for i in range(len(items)):\n",
    "            maxValue = max(maxValue, items[i][1])\n",
    "            prices.append(items[i][0])\n",
    "            beauties.append(maxValue)\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            index = bisect.bisect(prices, q) - 1\n",
    "            if index < 0:\n",
    "                res.append(0)\n",
    "            else:\n",
    "                res.append(beauties[index])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        items.sort()\n",
    "        n = len(items)\n",
    "        f = [0] * n\n",
    "        f[0] = items[0][1]\n",
    "        ret = []\n",
    "        for i in range(1, n):\n",
    "            f[i] = max(f[i - 1], items[i][1])\n",
    "        for q in queries:\n",
    "            l, r = 0, n - 1\n",
    "            while l <= r:\n",
    "                m = l + r >> 1\n",
    "                if items[m][0] <= q:\n",
    "                    l = m + 1\n",
    "                else:\n",
    "                    r = m - 1\n",
    "            ret.append(f[r] if r > -1 else 0)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        queries = sorted([[p,i] for i,p in enumerate(queries)])\n",
    "        n = len(queries)\n",
    "        result = [0]*n \n",
    "        items.sort()\n",
    "        i, left = 0, 0\n",
    "        maxBeauty = 0\n",
    "        while(i < n):\n",
    "            price, idx = queries[i]\n",
    "            while(left < len(items) and items[left][0] <= price):\n",
    "                maxBeauty = max(maxBeauty, items[left][1])\n",
    "                left += 1\n",
    "            result[idx] = maxBeauty\n",
    "            i += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        queries = sorted([[p,i] for i,p in enumerate(queries)])\n",
    "        n = len(queries)\n",
    "        result = [0]*n \n",
    "        items.sort()\n",
    "        i, left = 0, 0\n",
    "        maxBeauty = 0\n",
    "        while(i < n):\n",
    "            price, idx = queries[i]\n",
    "            while(left < len(items) and items[left][0] <= price):\n",
    "                maxBeauty = max(maxBeauty, items[left][1])\n",
    "                left += 1\n",
    "            result[idx] = maxBeauty\n",
    "            i += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        items.sort(key=lambda x: x[0])\n",
    "        for i, q in enumerate(queries):\n",
    "            queries[i] = (q << 32) | i\n",
    "        \n",
    "        queries.sort()\n",
    "        ans = [0] * len(queries)\n",
    "        max_, i = 0, 0\n",
    "\n",
    "        for q in queries:\n",
    "            while i < len(items) and items[i][0] <= (q >> 32):\n",
    "                max_ = max(max_, items[i][1])\n",
    "                i += 1 \n",
    "            ans[q & ((1 << 32) - 1)] = max_\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        queries = sorted([[p,i] for i,p in enumerate(queries)])\n",
    "        n = len(queries)\n",
    "        result = [0]*n \n",
    "        items.sort()\n",
    "        i, left = 0, 0\n",
    "        maxBeauty = 0\n",
    "        while(i < n):\n",
    "            price, idx = queries[i]\n",
    "            while(left < len(items) and items[left][0] <= price):\n",
    "                maxBeauty = max(maxBeauty, items[left][1])\n",
    "                left += 1\n",
    "            result[idx] = maxBeauty\n",
    "            i += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\r\n",
    "        res = {}\r\n",
    "        s = SortedList(items)\r\n",
    "        s2 = SortedList([i[::-1] for i in items])\r\n",
    "        for i in sorted(queries)[::-1]:\r\n",
    "            while s and s[-1][0] > i:\r\n",
    "                s2.remove(s.pop()[::-1])\r\n",
    "            res[i] = s2[-1][0] if s2 else 0\r\n",
    "        ans = []\r\n",
    "        for i in queries:\r\n",
    "            ans.append(res[i])\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        items.sort(key = lambda x: (x[0], -x[1]))\n",
    "        import bisect \n",
    "        beauties = []\n",
    "        prices = []\n",
    "        maxValue = 0\n",
    "        for i in range(len(items)):\n",
    "            maxValue = max(maxValue, items[i][1])\n",
    "            prices.append(items[i][0])\n",
    "            beauties.append(maxValue)\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            index = bisect.bisect(prices, q) - 1\n",
    "            if index < 0:\n",
    "                res.append(0)\n",
    "            else:\n",
    "                res.append(beauties[index])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        n = len(items)\n",
    "        max_q = {}\n",
    "        for price, beauty in items:\n",
    "            if price in max_q:\n",
    "                if beauty > max_q[price]:\n",
    "                    max_q[price] = beauty\n",
    "            else:\n",
    "                max_q[price] = beauty\n",
    "        max_key = sorted(max_q)\n",
    "        biggest = [0] * len(max_key)\n",
    "        tmp = 0\n",
    "        for i in range(len(max_key)):\n",
    "            tmp = max(tmp, max_q[max_key[i]])\n",
    "            biggest[i] = tmp\n",
    "\n",
    "        #print(max_q,max_key,biggest)\n",
    "        res = [0] * (len(queries))\n",
    "        for i, qu in enumerate(queries):\n",
    "            index = bisect_right(max_key, qu)\n",
    "            if index == len(max_key):\n",
    "                res[i] = biggest[-1]\n",
    "            else:\n",
    "                if index == 0:\n",
    "                    res[i] = 0\n",
    "                else:\n",
    "                    res[i] = biggest[index - 1]\n",
    "        \n",
    "        return res\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        items = sorted(items,key = lambda x:(x[0]))\n",
    "        res = []\n",
    "        max1 = items[0][1]\n",
    "        lst1 = []\n",
    "        lst2 = []\n",
    "        for i in range(len(items)):\n",
    "            lst1.append(items[i][0])\n",
    "            max1 = max(max1,items[i][1])\n",
    "            lst2.append(max1)\n",
    "        print(lst1,lst2)\n",
    "        for p in queries:\n",
    "            index = bisect.bisect(lst1,p)\n",
    "            if index > 0:\n",
    "                res.append(lst2[index-1])\n",
    "            else:\n",
    "                res.append(0)\n",
    "        return res\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * (n + 1)\n",
    "    \n",
    "    def update(self, i, mx):\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] = max(self.tree[i], mx)\n",
    "            i += i & -i\n",
    "    \n",
    "    def query(self, i):\n",
    "        mx = -inf\n",
    "        while i:\n",
    "            mx = max(mx, self.tree[i])\n",
    "            i -= i & -i\n",
    "        return mx\n",
    "\n",
    "class Solution:\n",
    "    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n",
    "        items.sort()\n",
    "        qs = sorted((q, i) for i, q in enumerate(queries))\n",
    "        i, n = 0, len(items)\n",
    "        s = set(p for p, _ in items) | set(queries)\n",
    "        mp = {x: i + 1 for i, x in enumerate(sorted(s))}\n",
    "        bit = BIT(len(mp))\n",
    "        res = [0] * len(queries)\n",
    "        for q, qi in qs:\n",
    "            while i < n and items[i][0] <= q:\n",
    "                bit.update(mp[items[i][0]], items[i][1])\n",
    "                i += 1\n",
    "            res[qi] = bit.query(mp[q])\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
